from __future__ import with_statement
from random import Random
from time import time
from sys import stdout
from khronos.utils import INF, Deque, Logger, CPUTracker, TimeDelta, Namespace

indline_fmt = "%40s = %s"

class STS(object):
    """Base class implementing the stochastic tree search algorithm for combinatorial optimization 
    problems. Subclasses should define the following methods (methods marked with * are advisable 
    but not mandatory, and methods marked with ** are completely optional):
        
        root()             # create the search's starting point (the tree's root node)
        copy(node)         # create an exact copy of a given node
        moves(node)        # list of moves ((data, score) pairs) available at the given node
        apply(node, move)  # modify a node by applying a given move
        objective(node)    # compute the objective function value for the given node
        
        *is_leaf(node)     # tell whether a node is a leaf or not
        *lower_bound(node) # compute a lower bound of the objective function for the given node
        *rank(node)        # compute the rank of a node (used for queue placement)
        
        **dive_path(node, moves) # choose the path of a dive from the list of available moves
        **dive_expand(node, moves, dive_path) # select which moves should be expanded 
                                              # to the queue during a dive
        **select_next()          # return the queue index of the next node to explore
        **extract_solution(node) # return the part of the node which contains the solution
        **leaf(node, z)          # used to gather data from leaf nodes
        **pruned(node, lb)       # used to gather data from pruned nodes
        
    See the documention on these methods for more information on their role in the algorithm. For 
    a detailed description of the base algorithm, see 'Stochastic tree search: an illustration 
    with the knapsack problem' by Joao P. Pedroso and Mikio Kubo."""
    __slots__ = ["queue", "queue_limit", "diving", "upper_bound", "optimal", 
                 "rng", "instance", "solutions", "meta", "running", "cpu", 
                 "cpu_limit", "iteration_limit", "improvement_limit", "log"]
    queue_limit_default = INF
    diving_default      = True
    log_default         = True
    
    def __init__(self, queue_limit=None, diving=None, log=None):
        """Setup the solver's configuration attributes."""
        if queue_limit is None: queue_limit = self.__class__.queue_limit_default
        if diving      is None: diving      = self.__class__.diving_default
        if log         is None: log         = self.__class__.log_default
        self.queue_limit = queue_limit
        self.diving = diving
        self.log = Logger(enabled=log, streams=xrange(5), show_name=False)
        # +++
        self.queue = Deque()
        self.upper_bound = INF
        self.optimal = -INF
        self.rng = Random()
        self.instance = None
        self.solutions = []
        self.meta = Namespace()
        self.running = False
        self.cpu = CPUTracker()
        self.cpu_limit = INF
        self.iteration_limit = INF
        self.improvement_limit = INF
        
    def solve(self, instance=None, cpu=INF, iterations=INF, improvements=INF, upper_bound=INF, 
              optimal=-INF, seed=None, queue_limit=None, diving=None, log=None):
        """Initialize the solver and start the search by calling run() if the search was
        not stopped after calling init(). If after init() the running flag is false, it
        means that some stoppage criteria was met, so run() is not called."""
        self.init(instance, cpu, iterations, improvements, upper_bound, 
                  optimal, seed, queue_limit, diving, log)
        if self.running:
            self.run(cpu - self.cpu.total, iterations - self.meta.Iterations, 
                     improvements - len(self.solutions), upper_bound)
                     
    def init(self, instance=None, cpu=INF, iterations=INF, improvements=INF, upper_bound=INF, 
             optimal=-INF, seed=None, queue_limit=None, diving=None, log=None):
        """Solver initialization routine. Initializes all solver attributes, builds the global 
        metadata dictionary, and calls the bootstrap() method to setup the search's starting 
        point before the main loop."""
        if instance is not None:
            self.instance = instance
        if seed is None:
            seed = int(time() * 1000)
        if queue_limit is not None:
            self.queue_limit = queue_limit
        if diving is not None:
            self.diving = diving
        if log is not None:
            self.log.set_enabled(log)
        # +++
        self.queue = Deque()
        self.upper_bound = upper_bound
        self.optimal = optimal
        self.rng.seed(seed)
        # +++
        self.solutions = []
        self.meta = Namespace(Iterations=0, 
                              Leaves=0, 
                              Pruned=0, 
                              Discarded=0, 
                              Expanded=0, 
                              Dives=0, 
                              Aborted=0, 
                              Metaheuristic=self.__class__.__name__, 
                              Queue_Limit=self.queue_limit, 
                              Diving=self.diving, 
                              Seed=seed, 
                              Instance=self.instance)
        # +++
        self.running = True
        self.cpu = CPUTracker()
        self.cpu_limit = cpu
        self.iteration_limit = iterations
        self.improvement_limit = improvements
        # Attribute initialization finished. Log metadata summary.
        self.log(" --- %s initialization --- " % (self.__class__.__name__,), width=100)
        for key, value in sorted(self.meta.iteritems()):
            self.log(indline_fmt % (key, value), width=100)
        # Setup the start of the search. This needs to be done before the 
        # main loop to create the root node and place it in the queue.
        with self.cpu.tracking():
            self.bootstrap()
            
    def bootstrap(self):
        """Create the root node and queue it before the main loop starts."""
        root = self.root()
        self.optimal = max(self.optimal, self.lower_bound(root))
        self.queue_node(root)
        
    def step(self, iterations=1):
        """Shortcut method. Equivalent to run(iterations=xxx)."""
        self.run(iterations=iterations)
        
    def improve(self, improvements=1):
        """Shortcut method. Equivalent to run(improvements=xxx)."""
        self.run(improvements=improvements)
        
    def run(self, cpu=INF, iterations=INF, improvements=INF, upper_bound=INF):
        """The body of the search. It starts by getting a node from the queue, and running a 
        loop where the node is explored, and a next node is fetched from the queue. The loop
        stops when the queue is empty, or some stoppage criteria has been met (e.g. cpu limit).
        
        IMPORTANT NOTE: An empty queue does not imply that the search tree has been exhausted 
        because some nodes may have been discarded during the search (due to limitation on the 
        size of the queue). However, if no nodes are discarded the search only stops when the 
        whole search tree has been explored. Note that this only implies global optimality if 
        the branching function (the moves() method) returns all possible movements for every 
        node, otherwise the optimal solution may be unintentionally left out of the search."""
        # Update all stoppage conditions.
        self.cpu_limit = self.cpu.total + cpu
        self.iteration_limit = self.meta.Iterations + iterations
        self.improvement_limit = len(self.solutions) + improvements
        # Update the upper bound if we decrease it, OR allow it to increase if we haven't
        # found any solutions so far (it doesn't make sense to increase it otherwise).
        if upper_bound < self.upper_bound or len(self.solutions) == 0:
            self.upper_bound = upper_bound
        # The main search loop from a very high level (tracked cpu).
        explore = self.dive if self.diving else self.expand
        with self.cpu.tracking():
            try:
                self.running = True
                current = self.advance()
                while self.running:
                    explore(current.node)
                    self.meta.Iterations += 1
                    current = self.advance()
            except KeyboardInterrupt:
                self.log("INTERRUPT: search interrupted manually.")
                self.running = False
                
    def advance(self):
        """Get the next node to explore (fetch() method) from the queue if possible. If the 
        queue is empty or the node (or cpu) limit is reached, the search stops. Otherwise the 
        fetch() method is called to retrieve the next node to be explored."""
        node = None
        while self.running and node is None:
            if len(self.queue) == 0:
                self.log("EMPTY QUEUE: discarded %d nodes." % (self.meta.Discarded,))
                self.running = False
            elif self.meta.Iterations >= self.iteration_limit:
                self.log("ITERATION LIMIT REACHED: %d iterations." % (self.meta.Iterations,))
                self.running = False
            elif self.cpu.total >= self.cpu_limit:
                self.log("CPU LIMIT REACHED: %s cpu seconds elapsed." % (self.cpu.total,))
                self.running = False
            else:
##                assert self.verify_queue() == 0
                node = self.fetch_next()
        return node
        
    def fetch_next(self):
        """Use the selection scheme (select_next() method) to get the index of the next node 
        to explore and pop that node from the queue."""
        return self.queue.pop_at(self.select_next())
        
    def expand(self, node, moves=None):
        """Expand a list of moves applied to a given node to create a list of child nodes. These
        child nodes are then placed in the queue if possible, to be explored later.
        IMPORTANT NOTE: The argument node is modified by this method. If the node should be kept
        intact, then be sure to pass a copy of the node to this function, e.g. expand(copy(node)).
        """
        if moves is None:
            moves = self.moves(node)
        moves.sort(key=move_score, reverse=True)
        worst = moves.pop()
        for move in moves:
            child = self.copy(node)
            self.apply(child, move)
            self.queue_node(child)
        # Apply the last (worst) move to the actual node only after all other children have 
        # been generated. This way we can use the node directly, avoiding one potentially 
        # expensive copy operation for each call to expand().
        self.apply(node, worst)
        self.queue_node(node)
        self.meta.Expanded += 1
        
    def dive(self, node, path_fnc=None, expand_fnc=None, abort=1.0):
        """Make a dive starting at the given node. The dive's path and expansion of nodes can 
        be controlled by the path_fnc() and expand_fnc() functions.
        The dive can also be aborted whenever the node's LB becomes >= than the current UB 
        times the abort value. Note that if the abort value is infinity, the dive will not 
        abort because the lower bound should never be equal to positive infinity.
        The return value of a dive consists of a tuple containing the final node, the z-value 
        (or LB at the time of abortion), and a boolean flag telling whether the dive finished 
        (went to a leaf) or aborted (when LB >= abort * UB). Summarizing, if:
            1) somewhere during the dive the node's LB >= abort * UB, the dive is aborted and 
               the current node, its lower bound, and a finish flag equal to False are returned.
            2) a leaf node is reached, then the leaf, its objective function value, and a finish
               flag equal to True are returned.
        Format of the return tuple: (node, z_or_LB, finish_flag)
        IMPORTANT NOTE: The argument node is modified by this method. If the node should be kept
        intact, then be sure to pass a copy of the node to this function, e.g. dive(copy(node)).
        """
        if path_fnc is None:
            path_fnc = self.dive_path
        if expand_fnc is None:
            expand_fnc = self.dive_expand
        abort_value = self.upper_bound * abort
        dive_running = True
        dive_value = INF
        dive_finished = False
        while dive_running:
            # Check moves available at the current node, extract the dive path from the move 
            # list, and select moves that should be expanded. If there are moves to be expanded, 
            # create a clone of the current node to make the expansion later.
            moves = self.moves(node)
            dive_path = path_fnc(node, moves)
            expansion_moves = expand_fnc(node, moves, dive_path)
            clone = None if len(expansion_moves) == 0 else self.copy(node)
            # Apply the dive move to the current node, check if the new current node is a leaf 
            # or if the abortion condition is met (LB >= UB * abort).
            self.apply(node, dive_path)
            if self.is_leaf(node):
                z = self.check_leaf(node)
                self.meta.Dives += 1
                dive_running = False
                dive_value = z
                dive_finished = True
            else:
                lower_bound = self.lower_bound(node)
                if lower_bound >= abort_value:
                    self.meta.Aborted += 1
                    dive_running = False
                    dive_value = lower_bound
            # Finally, expand any previously selected moves.
            if clone is not None:
                self.expand(clone, expansion_moves)
        return node, dive_value, dive_finished
        
    def queue_node(self, node):
        """Attempt to add a node to the queue. If the node is a leaf node, or its lower bound is 
        greater or equal to the current upper bound, the node is pruned (not added to the queue 
        with certainty that it cannot lead to improving solutions). If none of the previous 
        conditions occurs, the node is ranked and added to the queue if there is available queue 
        space. If the queue is full, the new node is queued if its rank is better (higher) than 
        the rank of the worst (leftmost) node in the queue. In this case, the worst node is 
        discarded in favor of the new node."""
        if self.is_leaf(node):
            self.check_leaf(node)
            return
        lower_bound = self.lower_bound(node)
        if lower_bound >= self.upper_bound:
            self.pruned(node, lower_bound)
            self.meta.Pruned += 1
            return
        # Now we calculate the node's rank, and add some random noise for tie breaking in the 
        # queue. If there is available space in the queue, we simply "insort" the node. If not,
        # we are unavoidably going to discard something. We compare the node's rank with the rank
        # of the leftmost (lowest rank) node in the queue:
        #   a) If the node's rank is higher, then we discard the old node and insort the new.
        #   b) Otherwise the new node is discarded and the old node is kept in the queue.
        rank = (self.rank(node), self.rng.random())
        if len(self.queue) < self.queue_limit:
            self.queue.insort(NodeWrapper(node, lower_bound, rank))
        else:
            worst = self.queue[0]
            if rank > worst.rank:
                assert self.queue.popleft() is worst
                self.queue.insort(NodeWrapper(node, lower_bound, rank))
            self.meta.Discarded += 1
            
    # --------------------------------------------
    def check_leaf(self, node):
        """Check a leaf node's objective function value. If it is less that the current upper 
        bound on the optimal objective function value, we build and add a solution to the 
        solution list, tighten the upper bound, and prune the queue with the new bound. The 
        search is stopped at this point if an optimal solution is found or the desired number 
        of improvements has been reached.
        NOTE: This method returns the objective function value of the given node."""
        z = self.objective(node)
        if z < self.upper_bound:
            self.log("IMPROVEMENT: %s -> %s" % (self.upper_bound, z), stream=4)
            self.upper_bound = z
            if z <= self.optimal:
                self.log("OPTIMAL SOLUTION: stopping search.", stream=4)
                self.running = False
            else:
                if len(self.queue) > 0:
                    self.prune_queue()
                if len(self.solutions) >= self.improvement_limit:
                    self.log("IMPROVEMENT LIMIT REACHED: stopping search.")
                    self.running = False
            self.add_solution(self.extract_solution(node), z)
        self.leaf(node, z)
        self.meta.Leaves += 1
        return z
        
    def prune_queue(self):
        """Queue pruning using an updated upper bound of the optimal objective function value 
        (z*). Nodes are removed from the queue if their lower bound is greater or equal to the 
        new upper bound, i.e. they cannot possibly lead to solutions better than the new upper 
        bound."""
        total = len(self.queue)
        pruned = 0
        kept = 0
        while kept < len(self.queue):
            if self.queue[0].lower_bound >= self.upper_bound:
                w = self.queue.popleft()
                self.pruned(w.node, w.lower_bound)
                pruned += 1
            else:
                self.queue.rotate(-1)
                kept += 1
        assert pruned + kept == total
        self.log("QUEUE PRUNING: Total %d, Kept %d, Pruned %d" % (total, kept, pruned))
        self.meta.Pruned += pruned
        
    def iter_queue(self):
        """Returns an iterator over the queue contents of the solver. This may be used by the 
        select_next() method, which returns the index of the next node to explore. The return 
        value of this method is a generator yielding (node, LB, rank, index) tuples."""
        for i, wrapper in enumerate(self.queue):
            yield wrapper.node, wrapper.lower_bound, wrapper.rank, i
            
    def verify_queue(self):
        """Perform a sanity check to the contents of the queue. If any node is out of order 
        (rank-wise) or a node's LB is greater or equal to the current LB, an error message is 
        printed. This method returns the number of errors that were caught."""
        errors = 0
        if len(self.queue) > 0:
            prev_rank = self.queue[0].rank
            for i, node in enumerate(self.queue):
                if node.lower_bound >= self.upper_bound:
                    self.log.error("Non-improving node at position %d" % (i,))
                    errors += 1
                if prev_rank > node.rank:
                    self.log.error("Rank inversion at position %d (%s > %s)" % 
                                   (i, prev_rank, node.rank))
                    errors += 1
                prev_rank = node.rank
        return errors
        
    def add_solution(self, solution, z):
        """Add an improving solution (leaf node) to the solution list. The solution is coupled 
        with a metadata dictionary containing a snapshot of the current status of the solver 
        (e.g. number of explored, discarded, pruned nodes, dives, z-value, cpu time, etc)."""
        meta = self.meta.copy()
        meta.update(Solution=solution, 
                    Objective=z, 
                    Queue_Size=len(self.queue), 
                    Search_Speed=(self.meta.Iterations + 1) / self.cpu.total, 
                    CPU=TimeDelta(seconds=self.cpu.total))
        self.solutions.append(meta)
        # Log the solution's metadata.
        self.log("=" * 80)
        for key, value in sorted(meta.iteritems()):
            self.log(indline_fmt % (key, value), width=80)
        self.log("=" * 80)
        
    def best_solution(self):
        """If at least one solution has been found, return the best of them. Note that the list 
        of solutions is ordered by decreasing z-value, so the last element of the list contains 
        our best solution. If the list is empty, None is returned.
        NOTE: a solution is a namespace containing the solution itself as well as additional data 
        about the search state at the time the solution was obtained."""
        if len(self.solutions) > 0:
            return self.solutions[-1]
        return None
        
    # --------------------------------------------
    def report(self, show_solutions=True, out=stdout):
        """Write a summary of the solver's configuration, current 
        search state and a summary of the solutions found so far."""
        fmt = indline_fmt + "\n"
        out.write(object.__repr__(self) + "\n")
        out.write(fmt % ("Explore method", "dive" if self.diving else "expand"))
        out.write(fmt % ("Queue limit", self.queue_limit))
        if self.instance is not None:
            qsize = len(self.queue)
            qoccupation = 100.0 * qsize / self.queue_limit
            gss = "%.3f iter/sec" % (self.meta.Iterations / self.cpu.total,)
            out.write(fmt % ("Queue size", "%d (%.3f %%)" % (qsize, qoccupation)))
            out.write(fmt % ("Total CPU time", TimeDelta(seconds=self.cpu.total)))
            out.write(fmt % ("Global search speed (GSS)", gss))
            out.write(fmt % ("Iterations",      self.meta.Iterations))
            out.write(fmt % ("Leaves reached",  self.meta.Leaves))
            out.write(fmt % ("Pruned nodes",    self.meta.Pruned))
            out.write(fmt % ("Discarded nodes", self.meta.Discarded))
            out.write(fmt % ("Expanded nodes",  self.meta.Expanded))
            out.write(fmt % ("Dives completed", self.meta.Dives))
            out.write(fmt % ("Dives aborted",   self.meta.Aborted))
            out.write(fmt % ("Upper bound", self.upper_bound))
            out.write(fmt % ("Solutions found", len(self.solutions)))
            if show_solutions:
                prev_iter = 0
                prev_cpu = 0.0
                for x, sol in enumerate(self.solutions):
                    iss = (sol.Iterations + 1 - prev_iter) / (sol.CPU.to_seconds() - prev_cpu)
                    prev_iter = sol.Iterations + 1
                    prev_cpu = sol.CPU.to_seconds()
                    sol_info = "%s (obtained at %s, ISS=%.3f iter/sec)" % \
                        (sol.Objective, sol.CPU, iss)
                    out.write(fmt % ("Solution %d" % (x,), sol_info))
                    
    def plot_solutions(self, filename=None, dpi=300):
        """Build and display or save a plot showing the evolution of the upper bound (aka the 
        best solution) over time. If filename is None, the plot is displayed to the screen, 
        otherwise it is saved to the specified file. The filename extension will determine the 
        format of the output file (e.g. pdf, eps, png, jpg)."""
        if len(self.solutions) == 0:
            print "Error: No solutions to be plotted."
            return
        meta = self.solutions[0]
        cpu = meta.CPU.to_seconds()
        objective = meta.Objective
        xs = [cpu]
        ys = [objective]
        for meta in self.solutions[1:]:
            cpu = meta.CPU.to_seconds()
            xs.append(cpu)
            ys.append(objective)
            objective = meta.Objective
            xs.append(cpu)
            ys.append(objective)
        xs.append(self.cpu.total)
        ys.append(self.upper_bound)
        
        from matplotlib.pyplot import figure
        fig = figure()
        plot = fig.add_subplot(1, 1, 1)
        plot.set_title("Upper bound over time")
        plot.set_xlabel("CPU time (s)")
        plot.set_ylabel("Upper bound")
        plot.plot(xs, ys, color="blue", linewidth=2, 
                  marker="o", markeredgecolor="blue")
        if filename is None:
            fig.show()
        else:
            fig.savefig(filename, dpi=dpi)
            
    def first_nodes(self, n=10):
        """Print the first n nodes on the queue."""
        n = min(n, len(self.queue))
        print "First %d nodes" % (n,)
        self.show_nodes(0, n)
        
    def last_nodes(self, n=10):
        """Print the last n nodes on the queue."""
        n = min(n, len(self.queue))
        print "Last %d nodes" % (n,)
        self.show_nodes(len(self.queue) - n, n)
        
    def edge_nodes(self, n=10):
        """Print the first and last n nodes on the queue."""
        self.first_nodes(n)
        self.last_nodes(n)
        
    def show_nodes(self, x=0, n=INF):
        """Print the part of the queue starting at index 'x' and ending 
        at index 'x+n-1' (n is the number of elements printed)."""
        end = min(x + n, len(self.queue))
        while x < end:
            print "\t", x, "::", self.queue[x]
            x += 1
            
    # --------------------------------------------
    def root(self): # MUST BE REDEFINED
        """Create and return the search's initial node."""
        raise NotImplementedError()
        
    def copy(self, node): # MUST BE REDEFINED
        """Create an exact copy of the given node. This method is extensively used because a lot
        of node copies are necessary while expanding a node's children. Extreme care should be 
        taken for shared information between nodes. If the shared data can somehow be modified 
        then each node should contain an independent copy of that data."""
        raise NotImplementedError()
        
    def moves(self, node): # MUST BE REDEFINED
        """Create a list of moves available at the given node. Each move consists of two parts: 
        data and score. The data part should contain all the necessary information to apply a 
        change to a node. The score part should contain any Python object that can be compared,
        either through __cmp__ or rich comparison methods (__gt__ and friends).
        The return value of this method should then be an iterable of (mv_data, mv_score) tuples.
        Higher move scores are interpreted as preferred by the heuristic, and will be explored 
        first by the algorithm if diving is enabled."""
        raise NotImplementedError()
        
    def apply(self, node, move): # MUST BE REDEFINED
        """Apply a move (a (mv_data, mv_score) pair, as returned by moves()) to a given node."""
        raise NotImplementedError()
        
    def objective(self, node): # MUST BE REDEFINED
        """Calculate and return the objective function value of a given leaf node."""
        raise NotImplementedError()
        
    def is_leaf(self, node): # SHOULD BE REDEFINED (TO INCREASE SPEED IN LEAF CHECKING)
        """Return a boolean indicating whether the given node is a leaf or not. It is advisable
        to redefine this method in subclasses, but it's default behavior should work ok, although
        much slower than with an application-specific 'leafness' check. By default, a node is 
        considered a leaf if its list of available moves is empty."""
        return len(self.moves(node)) == 0
        
    def lower_bound(self, node): # SHOULD BE REDEFINED (TO ALLOW PRUNING)
        """Calculate and return a lower bound of the best objective function value (z) that can 
        be obtained through the given node. This method should absolutely not return a value 
        which is not a real lower bound of the z-value, as this may cause incorrect pruning 
        decisions. The default value (-INF) disables pruning, since every node will have a lower
        bound that is smaller than the global upper bound of the z-value."""
        return -INF
        
    def rank(self, node): # SHOULD BE REDEFINED (TO ALLOW QUEUE ORDERING)
        """Calculate and return the rank of a given node. The rank is used to define the order 
        by which nodes are placed in the queue (low to high rank). If the next node selection 
        method (select_next()) selects the rightmost node everytime, then the search becomes 
        best-first search, and rank guides the search order.
        By default, a constant value is returned regardless of the node. This behavior can be 
        used, but note that it makes the search completely stochastic, since the order of 
        exploration of the nodes, as well as discarding decisions (if there is a queue size 
        limit), become completely ruled by the noise component of ranks."""
        return 0.0
        
    def dive_path(self, node, moves): # COMPLETELY OPTIONAL
        """This method is used in dives to guide the direction of the descent. Its arguments are 
        a node and the list of available moves at that node. The default behavior is to return 
        the first move with the maximum score, thus leading to a greedy dive."""
        return max(moves, key=move_score)
        
    def dive_expand(self, node, moves, dive_path): # COMPLETELY OPTIONAL
        """This method is used as the default function for selecting moves which should be 
        expanded during a dive. Its arguments are the current node from which we are expanding,
        the list of *all* moves (including the dive path), and the dive path seperately. The 
        return value should be a sublist of the argument move list. For each move in the returned
        list, a child node is created and queued for future exploration.
        By default, dive_expand() returns the entire non-dive path move list, leading to a full 
        expansion (classical) dive. For faster dives, one could for instance return an empty list 
        or tuple, making no expansion of child nodes to the queue."""
        moves.remove(dive_path)
        return moves
        
    def select_next(self): # COMPLETELY OPTIONAL
        """Return the index of the next node to explore from the queue. This method is used to 
        decide which point in the queue the next node is going to be taken from. The default 
        behavior is to simply return -1, making the next node always be at the right (high-rank) 
        end of the queue, which leads to best-first search. To define custom selection behavior, 
        the iter_queue() method may be used to inspect the contents of the queue."""
        return -1
        
    def extract_solution(self, node): # COMPLETELY OPTIONAL
        """This method is called when an improving leaf node is found. It should return only the 
        part of the node's state that contains data representing a solution to the problem. The 
        return value of this method is added to the solver's solution list together with the 
        solution's metadata dictionary. For instance, in a scheduling application, a node can 
        contain the whole state of a shop floor, but a solution is only the schedule that is 
        produced during the construction process, so we could create something like (in a 
        subclass):
            def extract_solution(self, shop):
                return shop.schedule
                
        IMPORTANT NOTE: This is only a commodity function, and it **is not necessary** for the 
        algorithm to work! The method's default behavior is fine, and has absolutely no influence 
        in the speed or quality of the results obtained. The default behavior is just to return 
        the whole leaf node, so it is stored in the solution list together with its metadata."""
        return node
        
    def leaf(self, node, z):
        """This method can be used to gather information from reached leaf nodes. This information 
        may be of extremme value to help guide the search, together with the pruned() method. The 
        arguments to this method are the leaf node and its objective function value z."""
        pass
        
    def pruned(self, node, lb):
        """This method can be used to gather information from pruned nodes. This information may 
        be of extremme value to help guide the search, together with the leaf() method. The 
        arguments to this methods are the pruned node and the node's lower bound."""
        pass
        
class NodeWrapper(object):
    """Node wrapper used to hold data necessary for the stochastic tree search algorithm.
    Attributes:
        node - The node's state information.
        lower_bound - A lower bound of the best z-value obtained through this node.
        rank - The node's rank (for ordering the queue).
    """
    __slots__ = ["node", "lower_bound", "rank"]
    
    def __init__(self, node, lower_bound, rank):
        self.node = node
        self.lower_bound = lower_bound
        self.rank = rank
        
    def __repr__(self):
        return "<Node(R=%s, LB=%s) at %s>" % (self.rank, self.lower_bound, hex(id(self)))
        
    def __cmp__(self, node):
        return cmp(self.rank, node.rank)
        
def move_score(move):
    """Support function, used as the 'key' argument to list.sort() and the max() function, for 
    sorting lists of moves or getting the highest-scored (greedy) move from a list of moves 
    returned by the moves() method, respectively."""
    mv_data, mv_score = move
    return mv_score
    
